#include "acengine.h"
#include <stddef.h>

#define __ACE_ANY_SIZE (1)
#define __ACE_TNB_INITIAL_SIZE (6)
#define __ACE_QUEUE_INITIAL_SIZE (64)

/* private structures */
struct __AceTrieNode
{
	AceByte data;
	char exist;
	void *key;
	int depth;
	_AceTrieNode *parent;
	_AceTrieNode *fail;
	_AceTrieNode *next[ACE_BYTE_MAX - ACE_BYTE_MIN];
};

struct __AceTNBlock;
typedef struct __AceTNBlock _AceTNBlock;

struct __AceTNBlock
{
	_AceTNBlock *prev;
	_AceTrieNode array[__ACE_ANY_SIZE];
};

struct __AceTNAllocator
{
	AceAllocator *allocator;
	_AceTNBlock *current;
	size_t array_size;
	size_t remaining;
};

struct __AceQueueNode;
typedef struct __AceQueueNode _AceQueueNode;

struct __AceQueue;
typedef struct __AceQueue _AceQueue;

struct __AceQueueNode
{
	size_t array_size;
	size_t front;
	size_t rear;
	_AceQueueNode *next;
	_AceTrieNode *array[__ACE_ANY_SIZE];
};

struct __AceQueue
{
	AceAllocator *allocator;
	_AceQueueNode *front;
	_AceQueueNode *rear;
	size_t array_size;
};

/* static function prototypes */
static _AceTNBlock * __ace_tnablock_alloc(AceAllocator *allocator, size_t array_size);
static _AceTNBlock * __ace_tnablock_free(_AceTNBlock *thiz, AceAllocator *allocator);

static void __ace_tna_initialize(_AceTNAllocator *thiz, AceAllocator *allocator);
static _AceTrieNode * __ace_tna_alloc(_AceTNAllocator *thiz,
	AceByte data, int depth, _AceTrieNode *parent);
static void __ace_tna_freeall(_AceTNAllocator *thiz);

static _AceQueueNode * __ace_queuenode_alloc(AceAllocator *allocator, size_t array_size);
static _AceQueueNode * __ace_queuenode_free(_AceQueueNode *thiz, AceAllocator *allocator);
static int __ace_queuenode_empty(_AceQueueNode *thiz);
static int __ace_queuenode_full(_AceQueueNode *thiz);
static void __ace_queuenode_push(_AceQueueNode *thiz, _AceTrieNode *data);
static _AceTrieNode * __ace_queuenode_front(_AceQueueNode *thiz);
static void __ace_queuenode_pop(_AceQueueNode *thiz);

static void __ace_queue_initialize(_AceQueue *thiz, AceAllocator *allocator);
static void __ace_queue_finalize(_AceQueue *thiz);
static AceStatus __ace_queue_push(_AceQueue *thiz, _AceTrieNode *data);
static _AceTrieNode * __ace_queue_front(_AceQueue *thiz);
static void __ace_queue_pop(_AceQueue *thiz);
static int __ace_queue_empty(_AceQueue *thiz);

/* implementation */
AceStatus ace_initialize(AceContext *thiz,
	AceAlloc *alloc_func, AceFree *free_func, void *alloc_context)
{
	_AceTNAllocator *tnallocator;

	thiz->allocator.alloc_func = alloc_func;
	thiz->allocator.free_func = free_func;
	thiz->allocator.context = alloc_context;
	
	tnallocator = (_AceTNAllocator *)(*alloc_func)(
		alloc_context, sizeof(_AceTNAllocator));

	if (tnallocator == NULL)
		return ACE_BAD_ALLOC;

	__ace_tna_initialize(tnallocator, &thiz->allocator);
	thiz->tnallocator = tnallocator;
	
	thiz->root = __ace_tna_alloc(thiz->tnallocator,
		ACE_BYTE_MIN, (size_t)-1, NULL);

	if (thiz->root == NULL)
	{
		(*free_func)(alloc_context, (void *)thiz->tnallocator);
		return ACE_BAD_ALLOC;
	}

	ace_reset(thiz);

	return ACE_SUCCESS;
}

void ace_finalize(AceContext *thiz)
{
	AceAllocator *allocator = &thiz->allocator;

	__ace_tna_freeall(thiz->tnallocator);
	(*allocator->free_func)(allocator->context, (void *)thiz->tnallocator);
}

AceStatus ace_insert_pattern(AceContext *thiz, AceByte *pattern, size_t size, void *key)
{
	size_t offset;
	_AceTrieNode *node = thiz->root;
	_AceTrieNode **next_ptr;

	for (offset = 0; offset != size; ++offset)
	{
		next_ptr = &node->next[pattern[offset] - ACE_BYTE_MIN];
		
		if (*next_ptr == NULL)
		{
			*next_ptr = __ace_tna_alloc(thiz->tnallocator,
				pattern[offset], node->depth + 1, node);

			if (*next_ptr == NULL)
				return ACE_BAD_ALLOC;
		}
		
		node = *next_ptr;
	}

	if (node->exist)
		return ACE_ALREADY_EXIST;

	node->exist = 1;
	node->key = key;

	return ACE_SUCCESS;
}

AceStatus ace_retrieve_key(AceContext *thiz, AceByte *pattern, size_t size, void **key)
{
	size_t offset;
	_AceTrieNode *node = thiz->root;
	
	for (offset = 0; offset != size; ++offset)
	{
		node = node->next[pattern[offset] - ACE_BYTE_MIN];
		
		if (node == NULL)
			return ACE_NOT_FOUND;
	}
	
	if (!node->exist)
		return ACE_NOT_FOUND;

	*key = node->key;
	return ACE_SUCCESS;
}

AceStatus ace_build_automation(AceContext *thiz)
{
	AceStatus status;
	_AceQueue queue;
	_AceTrieNode *node;
	int index;
	_AceTrieNode *parent;
	_AceTrieNode *next;

	__ace_queue_initialize(&queue, &thiz->allocator);
	status = __ace_queue_push(&queue, thiz->root);

	if (!ACE_SUCCESS(status))
	{
		__ace_queue_finalize(&queue);
		return status;
	}

	while (!__ace_queue_empty(&queue))
	{
		node = __ace_queue_front(&queue);
		__ace_queue_pop(&queue);

		for (index = ACE_BYTE_MIN; index < ACE_BYTE_MAX; ++index)
		{
			next = node->next[index - ACE_BYTE_MIN];

			if (next != NULL)
			{
				status = __ace_queue_push(&queue, next);

				if (!ACE_SUCCESS(status))
				{
					__ace_queue_finalize(&queue);
					return status;
				}
			}
		}

		if (node != thiz->root)
		{
			parent = node->parent->fail;
			next = NULL;
			
			while (parent != NULL)
			{
				next = parent->next[node->data - ACE_BYTE_MIN];
				
				if (next != NULL)
					break;
				
				parent = parent->fail;
			}

			if (next != NULL)
				node->fail = next;
			else
				node->fail = thiz->root;
		}
	}

	__ace_queue_finalize(&queue);
	return ACE_SUCCESS;
}

AceAction ace_append_text(AceContext *thiz, AceByte *buffer, size_t size,
	AceMatchCallback *callback, void *context)
{
	AceAction action;
	_AceTrieNode *parent;
	_AceTrieNode *next;
	_AceTrieNode *current = thiz->current;
	size_t offset = thiz->offset;

	while (size--)
	{
		while (1)
		{
			next = current->next[*buffer - ACE_BYTE_MIN];

			if (next != NULL || current == thiz->root)
				break;

			current = current->fail;
		}

		++buffer;
		++offset;

		if (next == NULL)
			continue;

		parent = current = next;

		while (parent != NULL)
		{
			if (parent->exist)
			{
				action = (*callback)(context,
					offset - parent->depth, parent->key);

				if (action != ACE_CONTINUE)
				{
					thiz->current = current;
					thiz->offset = offset;
					return action;
				}
			}
			
			parent = parent->fail;
		}
	}

	thiz->current = current;
	thiz->offset = offset;

	return ACE_CONTINUE;
}

void ace_reset(AceContext *thiz)
{
	thiz->current = thiz->root;
	thiz->offset = 0;
}

static _AceTNBlock * __ace_tnablock_alloc(AceAllocator *allocator, size_t array_size)
{
	_AceTNBlock *block;

	block = (_AceTNBlock *)(*allocator->alloc_func)(allocator->context,
		sizeof(_AceTNBlock) + (array_size - __ACE_ANY_SIZE) * sizeof(_AceTrieNode));

	return block;
}

static _AceTNBlock * __ace_tnablock_free(_AceTNBlock *thiz, AceAllocator *allocator)
{
	_AceTNBlock *prev;

	prev = thiz->prev;
	(*allocator->free_func)(allocator->context, (void *)thiz);

	return prev;
}

static void __ace_tna_initialize(_AceTNAllocator *thiz, AceAllocator *allocator)
{
	thiz->allocator = allocator;
	thiz->current = NULL;
	thiz->array_size = __ACE_TNB_INITIAL_SIZE;
	thiz->remaining = 0;
}

static _AceTrieNode * __ace_tna_alloc(_AceTNAllocator *thiz,
	AceByte data, int depth, _AceTrieNode *parent)
{
	size_t array_size;
	_AceTNBlock *block;
	_AceTrieNode *result;
	int index;

	if (thiz->remaining == 0)
	{
		array_size = thiz->array_size;
		block = __ace_tnablock_alloc(thiz->allocator, array_size);

		if (block == NULL)
			return NULL;

		block->prev = thiz->current;
		thiz->current = block;
		thiz->remaining = array_size;
		thiz->array_size = array_size + (array_size >> 1);
	}
	else
	{
		block = thiz->current;
	}

	result = &block->array[--thiz->remaining];
	result->data = data;
	result->exist = 0;
	result->depth = depth;
	result->parent = parent;
	result->fail = NULL;

	for (index = ACE_BYTE_MIN; index < ACE_BYTE_MAX; ++index)
		result->next[index - ACE_BYTE_MIN] = NULL;

	return result;
}

static void __ace_tna_freeall(_AceTNAllocator *thiz)
{
	_AceTNBlock *block = thiz->current;

	while (block != NULL)
		block = __ace_tnablock_free(block, thiz->allocator);
}

static _AceQueueNode * __ace_queuenode_alloc(AceAllocator *allocator, size_t array_size)
{
	_AceQueueNode *node;
	
	node = (_AceQueueNode *)(*allocator->alloc_func)(allocator->context,
		sizeof(_AceQueueNode) + (array_size - __ACE_ANY_SIZE) * sizeof(_AceTrieNode *));

	if (node != NULL)
	{
		node->array_size = array_size;
		node->front = 0;
		node->rear = 0;
		node->next = NULL;
	}

	return node;
}

static _AceQueueNode * __ace_queuenode_free(_AceQueueNode *thiz, AceAllocator *allocator)
{
	_AceQueueNode *next;
	
	next = thiz->next;
	(*allocator->free_func)(allocator->context, (void *)thiz);
	
	return next;
}

static int __ace_queuenode_empty(_AceQueueNode *thiz)
{
	return (thiz->front == thiz->rear);
}

static int __ace_queuenode_full(_AceQueueNode *thiz)
{
	return (thiz->front == thiz->rear + 1) ||
		(thiz->front == 0 && thiz->rear == thiz->array_size - 1);
}

static void __ace_queuenode_push(_AceQueueNode *thiz, _AceTrieNode *data)
{
	thiz->array[thiz->rear] = data;

	if (++thiz->rear == thiz->array_size)
		thiz->rear = 0;
}

static _AceTrieNode * __ace_queuenode_front(_AceQueueNode *thiz)
{
	return thiz->array[thiz->front];
}

static void __ace_queuenode_pop(_AceQueueNode *thiz)
{
	if (++thiz->front == thiz->array_size)
		thiz->front = 0;
}

static void __ace_queue_initialize(_AceQueue *thiz, AceAllocator *allocator)
{
	thiz->allocator = allocator;
	thiz->front = NULL;
	/* do not need to set thiz->rear */
	thiz->array_size = __ACE_QUEUE_INITIAL_SIZE;
}

static void __ace_queue_finalize(_AceQueue *thiz)
{
	_AceQueueNode *node = thiz->front;
	
	while (node != NULL)
		node = __ace_queuenode_free(node, thiz->allocator);
}

static AceStatus __ace_queue_push(_AceQueue *thiz, _AceTrieNode *data)
{
	_AceQueueNode *node;
	
	if (thiz->front == NULL)
	{
		node = __ace_queuenode_alloc(thiz->allocator, thiz->array_size);

		if (node == NULL)
			return ACE_BAD_ALLOC;

		/* should not increase array_size here */
		thiz->front = thiz->rear = node;
	}
	else if (__ace_queuenode_full(thiz->rear))
	{
		node = __ace_queuenode_alloc(thiz->allocator, thiz->array_size);

		if (node == NULL)
			return ACE_BAD_ALLOC;

		thiz->array_size += (thiz->array_size >> 1);
		thiz->rear->next = node;
		thiz->rear = node;
	}
	else
	{
		node = thiz->rear;
	}

	__ace_queuenode_push(node, data);
	return ACE_SUCCESS;
}

static _AceTrieNode * __ace_queue_front(_AceQueue *thiz)
{
	return __ace_queuenode_front(thiz->front);
}

static void __ace_queue_pop(_AceQueue *thiz)
{
	__ace_queuenode_pop(thiz->front);
	
	if (__ace_queuenode_empty(thiz->front))
	{
		thiz->front = __ace_queuenode_free(thiz->front, thiz->allocator);
	}
}

static int __ace_queue_empty(_AceQueue *thiz)
{
	return (thiz->front == NULL);
}

